package algo.A04_快速排序和归并排序;

/**
 * 分治法(divide and conquer，D&C):
 * 将原问题划分成若干个规模较小而结构与原问题一致的子问题;
 * 递归地解决这些子问题然后再合并其结果,就得到原问题的解。
 * <p>
 * 容易确定运行时间,是分治算法的优点之一。
 * <p>
 * 分治模式在每一层递归上都有三个步骤:
 * 分解(Divide) :将原问题分解成一系列子问题;
 * 解决(Conquer) :递归地解各子问题。若子问题足够小,则直接有解;
 * 合并(Combine):将子问题的结果合并成原问题的解。
 * <p>
 * 分治的关键点
 * <p>
 * 1.原问题可以一直分解为形式相同子问题,当子问题规模较小时,可自然求解,如一-个元素本身有序
 * 2.子问题的解通过合并可以得到原问题的解
 * 3.子问题的分解以及解的合并一定是比较简单的,则分解和合并所花的时间可能超出暴力解法,得不偿失
 */

import util.ArrayUtil;

/**
 * 快排的重点在于划分
 *
 * 步骤：
 * 分解:数组A[p…r]被划分为两个子数组A[p. .q-1]和A[q+1,r],使得A[q]为大小居中的数，
 *      左侧A[p. .q-1]中的每个元素都小于等于它，而右侧A[q+1,r]中的每个元素都大于等于它。其中计算下标q也是划分过程的一部分。
 *
 * 解决:通过递归调用快速排序，对子数组A[p. .q-1]和A[q+1,r]进行排序
 *
 * 合并:因为子数组都是原址排序的，所以不需要合并，数组A[p. .r]已经有序
 * 那么,划分就是问题的关键
 */

/**
 * 一遍单向扫描法:
 * 一遍扫描法的思路是，用两个指针将数组划分为三个区间
 * 扫描指针(scan_pos)左边是确认小于等于主元的
 * 扫描指针到某个指针(next_bigger_pos)中间为未知的，因此我们将第二个指针(next_bigger_pos) 称为未知区间末指针，末指针的右边区间为确认大于主元的元素
 */
public class M01_快速排序_单向扫描 {
    public static void main(String[] args) {
        int[] arr = ArrayUtil.getRandomArr(10, 1, 50);
        ArrayUtil.print(arr);
        quickSort(arr,0,arr.length-1);
        ArrayUtil.print(arr);
    }

    /**
     * 快速排序
     * @param A 原数组
     * @param p 数组左侧下标
     * @param r 数组右侧下标
     */
    private static void quickSort(int[] A, int p, int r) {
        if (p < r) {
            int q = partition(A, p, r);//执行分区方法，获取中点下标，中点左侧的元素都比中点小，右边都比中点大
            quickSort(A, p, q - 1);//对中点左侧的元素再次调用快速排序
            quickSort(A, q + 1, r);//对中点右侧的元素再次调用快速排序
        }
    }

    /**
     * 分区方法-单向扫描法
     * @param A 原数组
     * @param p 左侧数组下标
     * @param r 右侧数组下标
     * @return 完成一轮排序后基准所在的下标(中点)
     */
    private static int partition(int[] A, int p, int r) {
        int pivot = A[p];//把第一个元素作为基准
        int sp = p + 1;//扫描指针scan_pos
        int bigger = r;//右侧指针
        while (sp <= bigger) {//当扫描指针在右侧指针右边时退出循环
            if (A[sp] <= pivot) {//扫描到的元素<=基准，说明该元素就该放在左边，扫描指针直接右移即可
                sp++;
            } else {//扫描到的元素>基准，说明该元素就该放在右边，与右侧指针的元素交换，然后将右侧指针左移一位
                swap(A, sp, bigger);
                bigger--;
            }
        }
        //以上过程完成之后，sp一定指向第一个大于基准的(并且sp右边全都大于基准)，而bigger一定指向最后一个小于等于基准的(并且bigger左边全都小于等于基准)
        //我们要将基准放在中间的一个合适位置，这个位置就是当前bigger的位置
        swap(A, p, bigger);
        //上一行已经将基准放在了合适的位置(bigger指向的位置)，返回这个基准所在的位置
        return bigger;
    }

    /**
     * 交换数组中两个元素的方法
     */
    private static void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}
